{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Same Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSameTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相同的树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两棵二叉树的根节点 <code>p</code> 和 <code>q</code> ，编写一个函数来检验这两棵树是否相同。</p>\n",
    "\n",
    "<p>如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg\" style=\"width: 622px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>p = [1,2,3], q = [1,2,3]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg\" style=\"width: 382px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>p = [1,2], q = [1,null,2]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/12/20/ex3.jpg\" style=\"width: 622px; height: 182px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>p = [1,2,1], q = [1,1,2]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两棵树上的节点数目都在范围 <code>[0, 100]</code> 内</li>\n",
    "\t<li><code>-10<sup>4</sup> <= Node.val <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [same-tree](https://leetcode.cn/problems/same-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [same-tree](https://leetcode.cn/problems/same-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n[1,2,3]', '[1,2]\\n[1,null,2]', '[1,2,1]\\n[1,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        # Both trees are empty, they are the same\n",
    "        if p is None and q is None:\n",
    "            return True\n",
    "        # One of the trees is empty, they are not the same\n",
    "        if p is None or q is None:\n",
    "            return False\n",
    "        # The values of the nodes are different, they are not the same\n",
    "        if p.val != q.val:\n",
    "            return False\n",
    "        # Recursively check the left and right subtrees\n",
    "        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p, q):\n",
    "        \"\"\"\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if p==None and q==None:\n",
    "            return True\n",
    "        if p==None or q==None:\n",
    "            return False\n",
    "        if p.val==q.val:\n",
    "            return self.isSameTree(p.left,q.left)and self.isSameTree(p.right,q.right)\n",
    "        else:\n",
    "            return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p: 'TreeNode', q: 'TreeNode') -> 'bool':\n",
    "        # if p and q:\n",
    "        #     if p.val != q.val:\n",
    "        #         return False\n",
    "        #     if not self.isSameTree(p.left, q.left):\n",
    "        #         return False\n",
    "        #     if not self.isSameTree(p.right, q.right):\n",
    "        #         return False\n",
    "        #     return True\n",
    "        # elif not p and not q:\n",
    "        #     return True\n",
    "        # else:\n",
    "        #     return False\n",
    "        stack = [(p, q)]\n",
    "        while stack:\n",
    "            p, q = stack.pop(-1)\n",
    "            if p and q:\n",
    "                if p.val != q.val:\n",
    "                    return False\n",
    "                stack.append((p.left, q.left))\n",
    "                stack.append((p.right, q.right))\n",
    "            elif not p and not q:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p, q):\n",
    "        \"\"\"\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        p_queue = [p]\n",
    "        q_queue = [q]\n",
    "        while(p_queue or q_queue):\n",
    "            tmp_p_queue = []\n",
    "            tmp_p_val = []\n",
    "            # print(p_queue,q_queue)\n",
    "            if(set(p_queue)=={None} and set(q_queue)=={None}):\n",
    "                break\n",
    "            for i,node in enumerate(p_queue):\n",
    "                if node:\n",
    "                    tmp_p_val.append(node.val)\n",
    "                    tmp_p_queue.append(node.left)\n",
    "                    tmp_p_queue.append(node.right)\n",
    "                else:\n",
    "                    tmp_p_val.append(None)\n",
    "                    tmp_p_queue.append(None)\n",
    "                    tmp_p_queue.append(None)\n",
    "            p_queue = tmp_p_queue\n",
    "            \n",
    "            tmp_q_queue = []\n",
    "            tmp_q_val = []\n",
    "            for i,node in enumerate(q_queue):                \n",
    "                if node:\n",
    "                    tmp_q_val.append(node.val)\n",
    "                    tmp_q_queue.append(node.left)\n",
    "                    tmp_q_queue.append(node.right)\n",
    "                else:\n",
    "                    tmp_q_val.append(None)\n",
    "                    tmp_q_queue.append(None)\n",
    "                    tmp_q_queue.append(None)\n",
    "            q_queue = tmp_q_queue\n",
    "            # print(tmp_p_val,tmp_q_val)\n",
    "            if tmp_p_val!=tmp_q_val:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p, q):\n",
    "        \"\"\"\n",
    "        :type p: TreeNode\n",
    "        :type q: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if p == None or q == None:\n",
    "            if p == None and q == None:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif p.val != q.val:\n",
    "            return False\n",
    "        else:\n",
    "            return self.isSameTree(p.left, q.left) and  self.isSameTree(p.right, q.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if p is None and q is None:\n",
    "            return True\n",
    "        if p is None or q is None:\n",
    "            return False\n",
    "        if p.val != q.val:\n",
    "            return False\n",
    "        if not self.isSameTree(p.left, q.left):\n",
    "            return False\n",
    "        return self.isSameTree(p.right, q.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p, q):\n",
    "        stack = [(p, q)]\n",
    "        while stack:\n",
    "            node1, node2 = stack.pop()\n",
    "            if not node1 and not node2:\n",
    "                continue\n",
    "            elif None in [node1, node2]:\n",
    "                return False\n",
    "            else:\n",
    "                if node1.val != node2.val:\n",
    "                    return False\n",
    "                stack.append((node1.right, node2.right))\n",
    "                stack.append((node1.left, node2.left))\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if p == None and q == None:\n",
    "            return True\n",
    "        elif p is not None and q is not None:\n",
    "            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if not p and not q:return True\n",
    "        elif not p or not q:return False        \n",
    "        else:\n",
    "            if p.val == q.val:\n",
    "                return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "            else: return False        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if p == None and q == None:\n",
    "            return True\n",
    "        if (p!=None and q!=None):\n",
    "            if p.val == q.val:\n",
    "                return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)\n",
    "            else:\n",
    "                return False \n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if not p and not q: return True\n",
    "        if not p or not q: return False\n",
    "        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if not p and not q:  # 节点都为空\n",
    "            return True\n",
    "        elif not p or not q: # 一节点空一节点非空\n",
    "            return False\n",
    "        elif p.val != q.val: # 均非空但是值不相同\n",
    "            return False\n",
    "        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "         \n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "#         if not p and not q:\n",
    "#             return True\n",
    "#         elif not p or not q:\n",
    "#             return False\n",
    "#         elif p.val != q.val:\n",
    "#             return False\n",
    "#         return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if p and q and p.val == q.val:\n",
    "            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        elif p is not None and q is not None:\n",
    "            if p.val == q.val:\n",
    "                return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        temp_p = [p]\n",
    "        temp_q = [q]\n",
    "        while True:\n",
    "            node_p = temp_p.pop(0)\n",
    "            node_q = temp_q.pop(0)\n",
    "            if node_p is not None and node_q is not None:\n",
    "                if node_p.val != node_q.val:\n",
    "                    return False\n",
    "                temp_p.append(node_p.left)\n",
    "                temp_p.append(node_p.right)\n",
    "                temp_q.append(node_q.left)\n",
    "                temp_q.append(node_q.right)\n",
    "            elif node_p is None and node_q is None:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "            if len(temp_p)!=len(temp_q):\n",
    "                return False\n",
    "            if not temp_q or not temp_p:\n",
    "                return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        res = []\n",
    "        def inorder(root, res):\n",
    "            if root:\n",
    "                inorder(root.left, res)\n",
    "                res.append(root.val)\n",
    "                inorder(root.right, res)\n",
    "            res.append(None)\n",
    "            print(res)\n",
    "        s1, s2 = [], []\n",
    "        inorder(p, s1)\n",
    "        inorder(q, s2)\n",
    "        if s1 == s2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        # if not p and not q: return True\n",
    "        # if not p or not q: return False\n",
    "\n",
    "        # if p.val != q.val: return False\n",
    "\n",
    "        # return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "        from inspect import getgeneratorstate\n",
    "        if (not p) and (not q):\n",
    "            return True\n",
    "        elif not p:\n",
    "            return False\n",
    "        elif not q:\n",
    "            return False\n",
    "        \n",
    "        gen_p, gen_q = self.tree_iter(p), self.tree_iter(q)\n",
    "        \n",
    "        for i, j in zip(gen_p, gen_q):\n",
    "            if i != j:\n",
    "                return False\n",
    "\n",
    "        # zip()在其中一个迭代器返回StopIteration时就会返回StopIteration来结束for循环\n",
    "        # 手动调用next()来使两迭代器迭代次数匹配\n",
    "        try:\n",
    "            next(gen_q)\n",
    "        except StopIteration:\n",
    "            return getgeneratorstate(gen_p) == getgeneratorstate(gen_q)\n",
    "        \n",
    "    # 实现前序遍历迭代器\n",
    "    def tree_iter(self, tree):\n",
    "        stack = []\n",
    "        p = tree\n",
    "        while p or stack :\n",
    "            while p:\n",
    "                yield p.val\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            else:\n",
    "                yield None\n",
    "            node = stack.pop()\n",
    "            p = node.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        elif not p and q:\n",
    "            return False\n",
    "        elif p and not q:\n",
    "            return False\n",
    "        elif p.val!=q.val:\n",
    "            return False\n",
    "        if p and q:\n",
    "            return self.isSameTree(p.left,q.left) and  self.isSameTree(p.right,q.right)\n",
    "    \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        if p == None and q == None:\n",
    "            return True\n",
    "        elif p == None or q == None:\n",
    "            return False\n",
    "        else:\n",
    "            return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        if p is None or q is None:\n",
    "            return q is p\n",
    "        return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        #递归\n",
    "        if p == None and q != None: return False\n",
    "        elif p != None and q == None: return False\n",
    "        elif p == None and q == None: return True\n",
    "        elif p.val != q.val: return False\n",
    "\n",
    "        outside = self.isSameTree(p.left, q.left)\n",
    "        inside = self.isSameTree(p.right, q.right)        \n",
    "        isSame = outside and inside\n",
    "        return isSame"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        elif not p or not q:\n",
    "            return False\n",
    "        else:\n",
    "            if p.val == q.val:\n",
    "                return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        if not q and not p:\n",
    "            return True\n",
    "        if (not q and p) or (not p and q):\n",
    "            return False\n",
    "        ptree = deque()\n",
    "        qtree = deque()\n",
    "        ptree.append(p)\n",
    "        qtree.append(q)\n",
    "        while len(ptree) and len(qtree):\n",
    "            print(ptree)\n",
    "            print(qtree)\n",
    "            nodep = ptree.popleft() \n",
    "            nodeq = qtree.popleft()\n",
    "            flag1 = 0\n",
    "            flag2 = 0\n",
    "            if nodep.val == nodeq.val :             \n",
    "                if (nodep.left and nodeq.left) or (nodep.left== None and nodeq.left==None):\n",
    "                    flag1 = 1\n",
    "                    if (nodep.left and nodeq.left):\n",
    "                        ptree.append(nodep.left)\n",
    "                        qtree.append(nodeq.left)\n",
    "                if (nodep.right and nodeq.right) or (nodep.right== None and nodeq.right==None):\n",
    "                    flag2 = 1\n",
    "                    if (nodep.right and nodeq.right):\n",
    "                        ptree.append(nodep.right)\n",
    "                        qtree.append(nodeq.right)\n",
    "            if not flag1 or not flag2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        def fn(p, q):\n",
    "            if p is None and q is None:\n",
    "                return True\n",
    "            elif p is None or q is None:\n",
    "                return False\n",
    "            elif p.val == q.val:\n",
    "                return fn(p.left, q.left) and fn(p.right, q.right)\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return fn(p, q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        if p and not q:\n",
    "            return False\n",
    "        \n",
    "        if q and not p:\n",
    "            return False\n",
    "        \n",
    "        if not p and not q:\n",
    "            return True\n",
    "        \n",
    "        if p.val != q.val:\n",
    "            return False\n",
    "        \n",
    "        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if not p or not q:\n",
    "            return False\n",
    "        if p.val != q.val:\n",
    "            return False\n",
    "        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
